package madixin.t206;

import java.util.Stack;

class Solution {

    public ListNode reverseList(ListNode head) {

        ListNode pre = null;
        ListNode tmp = null;

        while (head != null) {
            tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }

        return pre;
    }

    /**
     * 递归法
     */
    public ListNode reverseList2(ListNode head) {
        // 如果当前要反转的节点为 null 或者反转链表为 null
        // head.next 为 null，即反转链表的尾结点不存在，即反转链表不存在
        if (head == null || head.next == null) return head;
        // 节点 p 其实就是反转链表的头节点
        ListNode p = reverseList(head.next);
        // 我们将反转链表的尾结点（head.next）的 next 指向当前即将反转的节点
        head.next.next = head;
        // 然后让当前节点变成反转链表的尾结点
        head.next = null;
        // 返回反转链表的头结点
        return p;
    }

    /**
     * 利用外部空间
     */
    public ListNode reverseList1(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();

        while (head != null) {
            stack.add(head);
            head = head.next;
        }

        if (stack.isEmpty()) {
            return null;
        }

        ListNode reverseHead = stack.peek();
        ListNode reverse = stack.peek();

        while (!stack.isEmpty()) {
            reverse = stack.pop();
            reverse.next = stack.isEmpty() ? null : stack.peek();
        }

        return reverseHead;
    }

    public static void main(String[] args) {

        Stack<ListNode> stack = new Stack<ListNode>();

        stack.peek();
    }
}